package 代码随想录.链表.链表相交;

import java.util.List;

/**
 * 面试题 02.07. 链表相交
 * link:https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
 *
 * @author ChenweiLin
 * @create 2021-12-14 10:34
 */
public class IntersectionOfTwoLinkedListsLcci {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(0);
        ListNode listNode2 = new ListNode(9);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(2);
        ListNode listNode5 = new ListNode(4);
        ListNode listNodeA = new ListNode(3);

        //创建相交链表
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNodeA.next = listNode4;

        ListNode intersectionNode = getIntersectionNode(listNode1, listNodeA);

        System.out.println(intersectionNode.val);


    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //tep1:伪头节点先算出两个链表的各自长度
        ListNode weiA = new ListNode(-1);
        weiA.next = headA;

        ListNode weiB = new ListNode(-1);
        weiB.next = headB;

        ListNode countA = weiA;
        ListNode countB = weiB;
        int sizeA = 0;
        int sizeB = 0;

        while (countA.next != null){
            sizeA++;
            countA = countA.next;
        }

        while (countB.next != null){
            sizeB++;
            countB = countB.next;
        }

        //tep2:将大的定位至size大-size小的位置
        if(sizeA>sizeB){
            for (int i = 0; i < sizeA - sizeB; i++) {
                headA = headA.next;
            }
        }else{
            for (int i = 0; i < sizeB - sizeA; i++) {
                headB = headB.next;
            }
        }

        while (headA != null || headB !=null){
            if (headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }

        return null;

    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
